A typical system architecture suitable for a small packet switch is illustrated in FIG. 1. The small packet switch 10 comprises several port cards 12 labeled port card #1 to port card #P, a packet bus 14, and a packet memory 16. The port cards each comprise a line interface 18, an ingress packet processor 20, and an egress packet processor 22. The small packet switch may contain other elements, such as a controller, not shown in FIG. 1.
In operation, packets arriving through the line interface 18 on the port card 12 are processed by the ingress packet processor 20, and sent through the packet bus 14, for temporary storage in queues in the packet memory 16. The packet memory queues are typically organized according to the destination of the packets, in this case port card 12. Once packets are available in the packet memory queues, they are transmitted from the packet memory 16 through the packet bus 14 to the destination port cards 12, for further processing in the egress packet processor 22 of the respective port card 12. The processed egress packets are then sent out through the line interface 18.
The purpose of the packet memory 16 is to buffer the packets temporarily when more packets arrive for a specific destination port card 12 than the port card 12 can accept.
Switch capacity may be defined as the sum of the bit rates of all line interfaces.
The type of small packet switch 10 illustrated in FIG. 1 is limited in capacity by the throughput of the packet bus and the access bandwidth of the single shared packet memory.
Another system architecture, also common in the prior art, is a large packet switch illustrated in FIG. 2. The large packet switch 30 comprises several port cards 32 and a switch fabric 34. The port cards 32 in the large packet switch 30 differ in a number of details from the port cards 12 of the small packet switch 10. The port card 32 comprises a fabric interface 36, a packet memory 38, a line interface 40, and ingress and egress packet processors 42 and 44 respectively.
In the large packet switch 30, there is no single shared packet memory (as in the small packet switch 10); rather, each port card 32 contains a separate packet memory 38. Packets arriving through the line interface 40 and the ingress packet processor 42 are sent through the fabric interface 36 to the switch fabric 34. The switch fabric 34 routes each packet to the destination port card 32, where the packets accumulate in queues of the packet memory 38. Packets are then removed from the packet memory 38 by the egress packet processor 44 and sent out through the line interface 40.
In the large packet switch 30, the bandwidth available through the switch fabric 34 is usually greater than the bandwidth of the line interface 40 in the port card 32, in order to accommodate the fluctuating packet traffic without the loss of packets. The packet memory 38 buffers and absorbs the statistical fluctuations in the amount of traffic arriving for the destination port card 32 from the switch fabric 34.
In a similar large switch architecture of the prior art, an ingress buffer 46 (shown in dotted lines in FIG. 2) is attached to the ingress packet processor. The ingress buffer 46 may be required if the bandwidth available through the switch fabric 34 is lower than the peak bandwidth from the line interface 40. The ingress buffer 46 is another form of packet memory.
The capacity of the large packet switch 30 is a function of the number of port cards 32 that can be supported by the switch fabric 34, and the capacity of each individual port card 32. The capacity of a port card 32 is largely determined by the bandwidth of the line interface 40. In a high capacity system, fibre optic line interfaces with a bit rate of 10 Gigabits per second are common at present. It is also possible to combine multiple fibre optic line interfaces on a single port card, to achieve even higher capacity.
While the bit rates available in fibre optic line interfaces have increased significantly in recent years, the speed available in the semiconductor technology used in the construction of packet memories has not progressed at the same rate. Consequently, architectural innovations are required to permit the construction of high capacity packet switches that contain packet memories.
An early innovation has been to use fixed size packets (cells). Variable size packets are segmented by the ingress packet processor (20 and 42) into fixed size cells before switching, and are reassembled into their original format by the egress packet processor (22 and 44). This innovation has allowed packet memories (16 and 38) to be based on a very wide bus, possibly as wide as the cell size. Recall that the overall access bandwidth of a memory is a function of the read/write speed and of the width of the memory bus. A typical switch cell size in the industry is 64 octets, resulting in a possible 512-bit wide memory bus.
A second consideration is the amount of memory required to implement a packet memory. As the capacity in terms of speed is increased, the amount of data (number of cells or packets) to be stored also increases. Very high-speed memory devices, for example static random access memory (SRAM), generally have lower storage capacity than slower devices, for example various forms of dynamic random access memory (DRAM). DRAM devices are common in the computer industry, and are obtainable at a much lower price per bit than the higher speed SRAM devices.
The problems due to the limitations of semiconductor memories have been recognized in recent years, and a number of solutions have been proposed which are based on the concept of dividing the packet memory into several banks, to achieve even greater parallelism than is available by merely using a wider bus.
U.S. Pat. No. 5,187,780 (Clark, et al.) describes a basic packet memory. The memory is divided into two zones to allow for simultaneous reading and writing in the same transfer cycle.
In the packet switch described in U.S. Pat. No. 6,160,814 (Ren, et al.) a multi-bank memory is used for a shared packet memory. During the storage process, cells are assigned to different memory modules in a cyclic assignment algorithm. The packet switch described in U.S. Pat. No. 6,160,814 is similar to the small packet switch 10 described in FIG. 1 above.
U.S. Pat. No. 6,314,489 (Nichols, et al.) describes a data cell storage system with a plurality of memory units for storing data cells (ATM cells) and a control memory for keeping track of the storage location of each cell.
The paper “Techniques for Fast Shared Memory Switches” by Sundar Iyer and Nick McKeown of Stanford University, unpublished manuscript, September 2001, available at http://klamath.stanford.edu/˜sundaes/Papers/Unpub/sharedmemv1.0.pdf at the Stanford University website at http://www.stanford.edu, offers a solution for a multi-bank packet buffer with FIFO (first-in, first-out) behavior. This paper describes an algorithm, which takes into account the row/column addressing peculiarities of DRAMs.
Two recent papers by Sailesh Kumar et al., “Implementing Parallel Packet Buffering, Parts I and II” (CommsDesign, Apr. 22 and Apr. 29, 2002, respectively, available at http://www.commsdesign.com/story/OEG20020422S0006 and http://www.commsdesign.com/story/OEG20020429S0008) contain a good academic discussion of the issue. These papers propose a Parallel Packet Buffering (PPB) algorithm in which the selection of the write destination buffer is explicitly based on “least occupancy”. Unfortunately, the algorithm has a finite probability of packet loss.
While a number of approaches have been proposed in the prior art for enhancing the capacity and speed of packet or cell storage memory, the need still exists for further development and alternative design of high-speed memory which would improve the memory performance and reduce the costs, while providing additional useful features.